# -*- coding: utf-8 -*-

'''
comb.py
Created on Junho de 2013
@author: 
    Ricardo Barros, ESTIG,  EI pós-laboral n.º 5137
    Sergio Santos, ESTIG,  EI pós-laboral n.º 5626
'''

"""
O algoritmo "Comb Sort"

Tempo de execução:
    Complexidade pior caso: O(n^2)



Carateristicas:
Este algoritmo faz parte da família de algoritmos de ordenação por troca. 
O Comb sort melhora o Bubble sort, e rivaliza com algoritmos como o Quicksort. 
A idéia básica é eliminar as tartarugas ou pequenos valores próximos do final 
da lista, já que em um bubble sort estes retardam a classificação tremendamente.

O Algoritmo repetidamente reordena diferentes pares de itens, separados por um salto, 
que é calculado a cada passagem. Método semelhante ao Bubble Sort, porém mais eficiente.

BIBLIOGRAFIA:
http://pt.wikipedia.org/wiki/Comb_sort

Como utilizar:
 - EXEMPLO: Ordenação do array A:
 
    A = [24, 452, 148, 145, 311, 316, 131, 393, 786, 564, 521, 660, 485, 287, 553, 274, 354, 285, 212, 625]
    print "antes A: ", A
    combSort(A)
    print "depois A:", A

RESULTADO:
antes A:  [24, 452, 148, 145, 311, 316, 131, 393, 786, 564, 521, 660, 485, 287,
553, 274, 354, 285, 212, 625]
depois A: [24, 131, 145, 148, 212, 274, 285, 287, 311, 316, 354, 393, 452, 485,
521, 553, 564, 625, 660, 786]
>>>
"""

def combSort(A):
    shrinkFactor = 1.247330950103979
    gap = len(A)
    swapped = True
    
    while ((gap > 1) or swapped):
        
        if gap > 1:
            gap = int(gap / shrinkFactor)
 
        swapped = False
        i = 0
 
        while (gap + i) < len(A):
            if A[i] > A[i + gap]:
                A[i], A[i + gap] = A[i + gap], A[i]
                swapped = True
            i = i + 1
    return A

    
def main():
    A = [24, 452, 148, 145, 311, 316, 131, 393, 786, 564, 521, 660, 485, 287, 553, 274, 354, 285, 212, 625]
    print "antes A: ", A
    combSort(A)
    print "depois A:", A

if __name__ == '__main__':
    main()

